/*
 * Copyright (c) 2009-2012, Salvatore Sanfilippo <antirez at gmail dot com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright notice,
 *     this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *   * Neither the name of Redis nor the names of its contributors may be used
 *     to endorse or promote products derived from this software without
 *     specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include "../lib/fmacros.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <unistd.h>
#include <sys/time.h>
#include <float.h>
#include <stdint.h>
#include <errno.h>

#include "../lib/util.h"

/* Glob-style pattern matching. */
int stringmatchlen ( const char *pattern, int patternLen,
                     const char *string, int stringLen, int nocase )
{
    while ( patternLen )
    {
        switch ( pattern[0] )
        {
            case '*':
                while ( pattern[1] == '*' )
                {
                    pattern ++;
                    patternLen --;
                }
                if ( patternLen == 1 )
                    return 1; /* match */
                while ( stringLen )
                {
                    if ( stringmatchlen (pattern + 1, patternLen - 1,
                                         string, stringLen, nocase) )
                        return 1; /* match */
                    string ++;
                    stringLen --;
                }
                return 0; /* no match */
                break;
            case '?':
                if ( stringLen == 0 )
                    return 0; /* no match */
                string ++;
                stringLen --;
                break;
            case '[':
            {
                int not, match;

                pattern ++;
                patternLen --;
                not = pattern[0] == '^';
                if ( not )
                {
                    pattern ++;
                    patternLen --;
                }
                match = 0;
                while ( 1 )
                {
                    if ( pattern[0] == '\\' )
                    {
                        pattern ++;
                        patternLen --;
                        if ( pattern[0] == string[0] )
                            match = 1;
                    }
                    else if ( pattern[0] == ']' )
                    {
                        break;
                    }
                    else if ( patternLen == 0 )
                    {
                        pattern --;
                        patternLen ++;
                        break;
                    }
                    else if ( pattern[1] == '-' && patternLen >= 3 )
                    {
                        int start = pattern[0];
                        int end = pattern[2];
                        int c = string[0];
                        if ( start > end )
                        {
                            int t = start;
                            start = end;
                            end = t;
                        }
                        if ( nocase )
                        {
                            start = tolower (start);
                            end = tolower (end);
                            c = tolower (c);
                        }
                        pattern += 2;
                        patternLen -= 2;
                        if ( c >= start && c <= end )
                            match = 1;
                    }
                    else
                    {
                        if ( ! nocase )
                        {
                            if ( pattern[0] == string[0] )
                                match = 1;
                        }
                        else
                        {
                            if ( tolower (( int ) pattern[0]) == tolower (( int ) string[0]) )
                                match = 1;
                        }
                    }
                    pattern ++;
                    patternLen --;
                }
                if ( not )
                    match = ! match;
                if ( ! match )
                    return 0; /* no match */
                string ++;
                stringLen --;
                break;
            }
            case '\\':
                if ( patternLen >= 2 )
                {
                    pattern ++;
                    patternLen --;
                }
                /* fall through */
            default:
                if ( ! nocase )
                {
                    if ( pattern[0] != string[0] )
                        return 0; /* no match */
                }
                else
                {
                    if ( tolower (( int ) pattern[0]) != tolower (( int ) string[0]) )
                        return 0; /* no match */
                }
                string ++;
                stringLen --;
                break;
        }
        pattern ++;
        patternLen --;
        if ( stringLen == 0 )
        {
            while ( *pattern == '*' )
            {
                pattern ++;
                patternLen --;
            }
            break;
        }
    }
    if ( patternLen == 0 && stringLen == 0 )
        return 1;
    return 0;
}

int stringmatch ( const char *pattern, const char *string, int nocase )
{
    return stringmatchlen (pattern, strlen (pattern), string, strlen (string), nocase);
}

/* Convert a string representing an amount of memory into the number of
 * bytes, so for instance memtoll("1Gb") will return 1073741824 that is
 * (1024*1024*1024).
 *
 * On parsing error, if *err is not NULL, it's set to 1, otherwise it's
 * set to 0. On error the function return value is 0, regardless of the
 * fact 'err' is NULL or not. */
long long memtoll ( const char *p, int *err )
{
    const char *u;
    char buf[128];
    long mul; /* unit multiplier */
    long long val;
    unsigned int digits;

    if ( err ) *err = 0;

    /* Search the first non digit character. */
    u = p;
    if ( *u == '-' ) u ++;
    while ( *u && isdigit (*u) ) u ++;
    if ( *u == '\0' || ! strcasecmp (u, "b") )
    {
        mul = 1;
    }
    else if ( ! strcasecmp (u, "k") )
    {
        mul = 1000;
    }
    else if ( ! strcasecmp (u, "kb") )
    {
        mul = 1024;
    }
    else if ( ! strcasecmp (u, "m") )
    {
        mul = 1000 * 1000;
    }
    else if ( ! strcasecmp (u, "mb") )
    {
        mul = 1024 * 1024;
    }
    else if ( ! strcasecmp (u, "g") )
    {
        mul = 1000L * 1000 * 1000;
    }
    else if ( ! strcasecmp (u, "gb") )
    {
        mul = 1024L * 1024 * 1024;
    }
    else
    {
        if ( err ) *err = 1;
        return 0;
    }

    /* Copy the digits into a buffer, we'll use strtoll() to convert
     * the digit (without the unit) into a number. */
    digits = u - p;
    if ( digits >= sizeof (buf ) )
    {
        if ( err ) *err = 1;
        return 0;
    }
    memcpy (buf, p, digits);
    buf[digits] = '\0';

    char *endptr;
    errno = 0;
    val = strtoll (buf, &endptr, 10);
    if ( ( val == 0 && errno == EINVAL ) || * endptr != '\0' )
    {
        if ( err ) *err = 1;
        return 0;
    }
    return val*mul;
}

/* Return the number of digits of 'v' when converted to string in radix 10.
 * See ll2string() for more information. */
uint32_t digits10 ( uint64_t v )
{
    if ( v < 10 ) return 1;
    if ( v < 100 ) return 2;
    if ( v < 1000 ) return 3;
    if ( v < 1000000000000UL )
    {
        if ( v < 100000000UL )
        {
            if ( v < 1000000 )
            {
                if ( v < 10000 ) return 4;
                return 5 + ( v >= 100000 );
            }
            return 7 + ( v >= 10000000UL );
        }
        if ( v < 10000000000UL )
        {
            return 9 + ( v >= 1000000000UL );
        }
        return 11 + ( v >= 100000000000UL );
    }
    return 12 + digits10 (v / 1000000000000UL);
}

/* Like digits10() but for signed values. */
uint32_t sdigits10 ( int64_t v )
{
    if ( v < 0 )
    {
        /* Abs value of LLONG_MIN requires special handling. */
        uint64_t uv = ( v != LLONG_MIN ) ?
            ( uint64_t ) - v : ( ( uint64_t ) LLONG_MAX ) + 1;
        return digits10 (uv) + 1; /* +1 for the minus. */
    }
    else
    {
        return digits10 (v);
    }
}

/* Convert a long long into a string. Returns the number of
 * characters needed to represent the number.
 * If the buffer is not big enough to store the string, 0 is returned.
 *
 * Based on the following article (that apparently does not provide a
 * novel approach but only publicizes an already used technique):
 *
 * https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920
 *
 * Modified in order to handle signed integers since the original code was
 * designed for unsigned integers. */
int ll2string ( char* dst, size_t dstlen, long long svalue )
{
    static const char digits[201] =
        "0001020304050607080910111213141516171819"
        "2021222324252627282930313233343536373839"
        "4041424344454647484950515253545556575859"
        "6061626364656667686970717273747576777879"
        "8081828384858687888990919293949596979899";
    int negative;
    unsigned long long value;

    /* The main loop works with 64bit unsigned integers for simplicity, so
     * we convert the number here and remember if it is negative. */
    if ( svalue < 0 )
    {
        if ( svalue != LLONG_MIN )
        {
            value = - svalue;
        }
        else
        {
            value = ( ( unsigned long long ) LLONG_MAX ) + 1;
        }
        negative = 1;
    }
    else
    {
        value = svalue;
        negative = 0;
    }

    /* Check length. */
    uint32_t const length = digits10 (value) + negative;
    if ( length >= dstlen ) return 0;

    /* Null term. */
    uint32_t next = length;
    dst[next] = '\0';
    next --;
    while ( value >= 100 )
    {
        int const i = ( value % 100 ) * 2;
        value /= 100;
        dst[next] = digits[i + 1];
        dst[next - 1] = digits[i];
        next -= 2;
    }

    /* Handle last 1-2 digits. */
    if ( value < 10 )
    {
        dst[next] = '0' + ( uint32_t ) value;
    }
    else
    {
        int i = ( uint32_t ) value * 2;
        dst[next] = digits[i + 1];
        dst[next - 1] = digits[i];
    }

    /* Add sign. */
    if ( negative ) dst[0] = '-';
    return length;
}

/* Convert a string into a long long. Returns 1 if the string could be parsed
 * into a (non-overflowing) long long, 0 otherwise. The value will be set to
 * the parsed value when appropriate. */
int string2ll ( const char *s, size_t slen, long long *value )
{
    const char *p = s;
    size_t plen = 0;
    int negative = 0;
    unsigned long long v;

    if ( plen == slen )
        return 0;

    /* Special case: first and only digit is 0. */
    if ( slen == 1 && p[0] == '0' )
    {
        if ( value != NULL ) *value = 0;
        return 1;
    }

    if ( p[0] == '-' )
    {
        negative = 1;
        p ++;
        plen ++;

        /* Abort on only a negative sign. */
        if ( plen == slen )
            return 0;
    }

    /* First digit should be 1-9, otherwise the string should just be 0. */
    if ( p[0] >= '1' && p[0] <= '9' )
    {
        v = p[0] - '0';
        p ++;
        plen ++;
    }
    else if ( p[0] == '0' && slen == 1 )
    {
        *value = 0;
        return 1;
    }
    else
    {
        return 0;
    }

    while ( plen < slen && p[0] >= '0' && p[0] <= '9' )
    {
        if ( v > ( ULLONG_MAX / 10 ) ) /* Overflow. */
            return 0;
        v *= 10;

        if ( v > ( ULLONG_MAX - ( p[0] - '0' ) ) ) /* Overflow. */
            return 0;
        v += p[0] - '0';

        p ++;
        plen ++;
    }

    /* Return if not all bytes were used. */
    if ( plen < slen )
        return 0;

    if ( negative )
    {
        if ( v > ( ( unsigned long long ) ( - ( LLONG_MIN + 1 ) ) + 1 ) ) /* Overflow. */
            return 0;
        if ( value != NULL ) *value = - v;
    }
    else
    {
        if ( v > LLONG_MAX ) /* Overflow. */
            return 0;
        if ( value != NULL ) *value = v;
    }
    return 1;
}

/* Convert a string into a long. Returns 1 if the string could be parsed into a
 * (non-overflowing) long, 0 otherwise. The value will be set to the parsed
 * value when appropriate. */
int string2l ( const char *s, size_t slen, long *lval )
{
    long long llval;

    if ( ! string2ll (s, slen, &llval) )
        return 0;

    if ( llval < LONG_MIN || llval > LONG_MAX )
        return 0;

    *lval = ( long ) llval;
    return 1;
}

/* Convert a double to a string representation. Returns the number of bytes
 * required. The representation should always be parsable by strtod(3). */
int d2string ( char *buf, size_t len, double value )
{
    if ( isnan (value) )
    {
        len = snprintf (buf, len, "nan");
    }
    else if ( isinf (value) )
    {
        if ( value < 0 )
            len = snprintf (buf, len, "-inf");
        else
            len = snprintf (buf, len, "inf");
    }
    else if ( value == 0 )
    {
        /* See: http://en.wikipedia.org/wiki/Signed_zero, "Comparisons". */
        if ( 1.0 / value < 0 )
            len = snprintf (buf, len, "-0");
        else
            len = snprintf (buf, len, "0");
    }
    else
    {
#if (DBL_MANT_DIG >= 52) && (LLONG_MAX == 0x7fffffffffffffffLL)
        /* Check if the float is in a safe range to be casted into a
         * long long. We are assuming that long long is 64 bit here.
         * Also we are assuming that there are no implementations around where
         * double has precision < 52 bit.
         *
         * Under this assumptions we test if a double is inside an interval
         * where casting to long long is safe. Then using two castings we
         * make sure the decimal part is zero. If all this is true we use
         * integer printing function that is much faster. */
        double min = - 4503599627370495; /* (2^52)-1 */
        double max = 4503599627370496; /* -(2^52) */
        if ( value > min && value < max && value == ( ( double ) ( ( long long ) value ) ) )
            len = ll2string (buf, len, ( long long ) value);
        else
#endif
            len = snprintf (buf, len, "%.17g", value);
    }

    return len;
}

/* Given the filename, return the absolute path as an SDS string, or NULL
 * if it fails for some reason. Note that "filename" may be an absolute path
 * already, this will be detected and handled correctly.
 *
 * The function does not try to normalize everything, but only the obvious
 * case of one or more "../" appearning at the start of "filename"
 * relative path. */
sds getAbsolutePath ( char *filename )
{
    char cwd[1024];
    sds abspath;
    sds relpath = sdsnew (filename);

    relpath = sdstrim (relpath, " \r\n\t");
    if ( relpath[0] == '/' ) return relpath; /* Path is already absolute. */

    /* If path is relative, join cwd and relative path. */
    if ( getcwd (cwd, sizeof (cwd )) == NULL )
    {
        sdsfree (relpath);
        return NULL;
    }
    abspath = sdsnew (cwd);
    if ( sdslen (abspath) && abspath[sdslen (abspath) - 1] != '/' )
        abspath = sdscat (abspath, "/");

    /* At this point we have the current path always ending with "/", and
     * the trimmed relative path. Try to normalize the obvious case of
     * trailing ../ elements at the start of the path.
     *
     * For every "../" we find in the filename, we remove it and also remove
     * the last element of the cwd, unless the current cwd is "/". */
    while ( sdslen (relpath) >= 3 &&
            relpath[0] == '.' && relpath[1] == '.' && relpath[2] == '/' )
    {
        sdsrange (relpath, 3, - 1);
        if ( sdslen (abspath) > 1 )
        {
            char *p = abspath + sdslen (abspath) - 2;
            int trimlen = 1;

            while ( *p != '/' )
            {
                p --;
                trimlen ++;
            }
            sdsrange (abspath, 0, - ( trimlen + 1 ));
        }
    }

    /* Finally glue the two parts together. */
    abspath = sdscatsds (abspath, relpath);
    sdsfree (relpath);
    return abspath;
}

/* Return true if the specified path is just a file basename without any
 * relative or absolute path. This function just checks that no / or \
 * character exists inside the specified path, that's enough in the
 * environments where Redis runs. */
int pathIsBaseName ( char *path )
{
    return strchr (path, '/') == NULL && strchr (path, '\\') == NULL;
}

#ifdef REDIS_TEST
#include <assert.h>

static void test_string2ll ( void )
{
    char buf[32];
    long long v;

    /* May not start with +. */
    strcpy (buf, "+1");
    assert (string2ll (buf, strlen (buf), &v) == 0);

    /* Leading space. */
    strcpy (buf, " 1");
    assert (string2ll (buf, strlen (buf), &v) == 0);

    /* Trailing space. */
    strcpy (buf, "1 ");
    assert (string2ll (buf, strlen (buf), &v) == 0);

    /* May not start with 0. */
    strcpy (buf, "01");
    assert (string2ll (buf, strlen (buf), &v) == 0);

    strcpy (buf, "-1");
    assert (string2ll (buf, strlen (buf), &v) == 1);
    assert (v == - 1);

    strcpy (buf, "0");
    assert (string2ll (buf, strlen (buf), &v) == 1);
    assert (v == 0);

    strcpy (buf, "1");
    assert (string2ll (buf, strlen (buf), &v) == 1);
    assert (v == 1);

    strcpy (buf, "99");
    assert (string2ll (buf, strlen (buf), &v) == 1);
    assert (v == 99);

    strcpy (buf, "-99");
    assert (string2ll (buf, strlen (buf), &v) == 1);
    assert (v == - 99);

    strcpy (buf, "-9223372036854775808");
    assert (string2ll (buf, strlen (buf), &v) == 1);
    assert (v == LLONG_MIN);

    strcpy (buf, "-9223372036854775809"); /* overflow */
    assert (string2ll (buf, strlen (buf), &v) == 0);

    strcpy (buf, "9223372036854775807");
    assert (string2ll (buf, strlen (buf), &v) == 1);
    assert (v == LLONG_MAX);

    strcpy (buf, "9223372036854775808"); /* overflow */
    assert (string2ll (buf, strlen (buf), &v) == 0);
}

static void test_string2l ( void )
{
    char buf[32];
    long v;

    /* May not start with +. */
    strcpy (buf, "+1");
    assert (string2l (buf, strlen (buf), &v) == 0);

    /* May not start with 0. */
    strcpy (buf, "01");
    assert (string2l (buf, strlen (buf), &v) == 0);

    strcpy (buf, "-1");
    assert (string2l (buf, strlen (buf), &v) == 1);
    assert (v == - 1);

    strcpy (buf, "0");
    assert (string2l (buf, strlen (buf), &v) == 1);
    assert (v == 0);

    strcpy (buf, "1");
    assert (string2l (buf, strlen (buf), &v) == 1);
    assert (v == 1);

    strcpy (buf, "99");
    assert (string2l (buf, strlen (buf), &v) == 1);
    assert (v == 99);

    strcpy (buf, "-99");
    assert (string2l (buf, strlen (buf), &v) == 1);
    assert (v == - 99);

#if LONG_MAX != LLONG_MAX
    strcpy (buf, "-2147483648");
    assert (string2l (buf, strlen (buf), &v) == 1);
    assert (v == LONG_MIN);

    strcpy (buf, "-2147483649"); /* overflow */
    assert (string2l (buf, strlen (buf), &v) == 0);

    strcpy (buf, "2147483647");
    assert (string2l (buf, strlen (buf), &v) == 1);
    assert (v == LONG_MAX);

    strcpy (buf, "2147483648"); /* overflow */
    assert (string2l (buf, strlen (buf), &v) == 0);
#endif
}

static void test_ll2string ( void )
{
    char buf[32];
    long long v;
    int sz;

    v = 0;
    sz = ll2string (buf, sizeof buf, v);
    assert (sz == 1);
    assert (! strcmp (buf, "0"));

    v = - 1;
    sz = ll2string (buf, sizeof buf, v);
    assert (sz == 2);
    assert (! strcmp (buf, "-1"));

    v = 99;
    sz = ll2string (buf, sizeof buf, v);
    assert (sz == 2);
    assert (! strcmp (buf, "99"));

    v = - 99;
    sz = ll2string (buf, sizeof buf, v);
    assert (sz == 3);
    assert (! strcmp (buf, "-99"));

    v = - 2147483648;
    sz = ll2string (buf, sizeof buf, v);
    assert (sz == 11);
    assert (! strcmp (buf, "-2147483648"));

    v = LLONG_MIN;
    sz = ll2string (buf, sizeof buf, v);
    assert (sz == 20);
    assert (! strcmp (buf, "-9223372036854775808"));

    v = LLONG_MAX;
    sz = ll2string (buf, sizeof buf, v);
    assert (sz == 19);
    assert (! strcmp (buf, "9223372036854775807"));
}

#define UNUSED(x) (void)(x)

int utilTest ( int argc, char **argv )
{
    UNUSED (argc);
    UNUSED (argv);

    test_string2ll ();
    test_string2l ();
    test_ll2string ();
    return 0;
}
#endif
